package forth

/*
	输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。

	假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

	示例 1:
	Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
	Output: [3,9,20,null,null,15,7]
	示例 2:

	Input: preorder = [-1], inorder = [-1]
	Output: [-1]
	限制：

	0 <= 节点个数 <= 5000

	来源：力扣（LeetCode）
	链接：https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof
	著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/
func BuildTree(preorder []int, inorder []int) *TreeNode {
	return buildTree(preorder, inorder)
}
func buildTree(preorder []int, inorder []int) *TreeNode {
	return _buildTree(preorder, inorder)
}

func _buildTree(preorder []int, inorder []int) *TreeNode {
	if len(preorder) == 0 || len(inorder) == 0 {
		return nil
	}
	rootValue := preorder[0]
	rootIndex := 0 // 根节点在inorder中的索引
	for i := 0; i < len(inorder); i++ {
		if inorder[i] == rootValue {
			rootIndex = i
			break
		}
	}
	root := &TreeNode{Val: rootValue}
	root.Left = _buildTree(preorder[1:rootIndex+1], inorder[:rootIndex])
	root.Right = _buildTree(preorder[rootIndex+1:], inorder[rootIndex+1:])
	return root
}
